'''
小根堆
'''
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists: return
        import heapq
        temp = []
        for i in lists:
            while i:
                heapq.heappush(temp,i.val)
                i = i.next
        cur = res = ListNode(0)
        while temp:
            cur.next = ListNode(heappop(temp))
            cur = cur.next
        return res.next

'''
列表,暴力新建链表
'''
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists: return
        result = []
        for i in lists:
            while i:
                result.append(i.val)
                i = i.next
        result.sort()
        point = head = ListNode(0)
        for i in result:
            point.next = ListNode(i)
            point = point.next
        return head.next
'''
归并 + 合并两个链表
'''
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists: return
        # 通过mid将数组一分为二，并不断缩小规模，当规模为1时返回并开始合并
        # 通过合并两个链表，不断增大其规模，整体看就是不断缩小-最后不断扩大的过程
        def helper(begin,end):
            if begin==end:
                return lists[begin]
            mid = begin+(end-begin)//2
            left = helper(begin,mid)
            right = helper(mid+1,end)
            return merge(left,right)
        # 合并两个有序链表
        def merge(l1,l2):
            if l1 and l2:
                if l1.val > l2.val: l1, l2 = l2, l1
                l1.next = merge(l1.next,l2)
            return l1 or l2
        return sorts(0,len(lists)-1)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        length = len(lists)
        # 边界情况
        if length == 0: return
        # 分到最后返回,递归的终止条件
        if length == 1: return lists[0]
        # 分治
        mid = length // 2
        return self.merge(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:]))

        # 合并两个有序链表

    def merge(self, l1, l2):
        if l1 and l2:
            if l1.val > l2.val: l1, l2 = l2, l1
            l1.next = self.merge(l1.next, l2)
        return l1 or l2